#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include <debug.h>
#include "threads/thread.h"
#include "threads/palloc.h"
#include "threads/malloc.h"
#include "threads/vaddr.h"
#include "userprog/pagedir.h"
#include "vm/frame.h"
#include "vm/page.h"
#include "vm/swap.h"
#ifdef _TEST_
#include "lib/stdio.h"
#endif

struct frame_table_entry
{
	void *upage; 					/* Address of user page, if any, that currently occupies this frame. */
	struct thread *owner;	/* Thread that owns this frame. */
};

struct frame_table_entry *frame_table;
uint32_t frame_table_length;
uint32_t next_frame_idx; /* Used for clock algorithm. */
struct lock frame_table_lock;

size_t get_frame_index (void *kpage);
bool is_frame_table_full (void);

/* Initializes the frame table. */
void frame_table_init (void)
{
	extern size_t user_page_cnt; /* palloc.c */
	frame_table = malloc (sizeof (struct frame_table_entry) * user_page_cnt);

	if (frame_table == NULL)
		PANIC ("Not enough memory for frame table.");

	frame_table_length = user_page_cnt;
	next_frame_idx = 0; 

	/* Initialize each frame table entry. */
	size_t i;
	for (i=0; i<frame_table_length; i++)
	{
		(frame_table + i)->upage = NULL;
		(frame_table + i)->owner = NULL;
	}

	lock_init (&frame_table_lock);
}

/* Get a frame for a user page from the "user pool", 
	 and returns its kernel virtual address. */
void *get_frame (bool zero)
{
	if (lock_held_by_current_thread (&frame_table_lock))
		return NULL;

	/* Lock acquired here will be released in 
		 frametable_set_frame where frametable modification completes. */
	lock_acquire (&frame_table_lock);

	enum palloc_flags flag = zero ? PAL_USER | PAL_ZERO : PAL_USER;
	void *kpage = palloc_get_page (flag);
		
	/* No pages are available. */
	if (kpage == NULL)
	{
		/* Choose a frame to evict. */
		uint32_t frame_idx = get_frame_to_evict ();
		
		/* Remove references to the frame from page directory that refers to it. */
		void *upage_to_evict = frame_table[frame_idx].upage;
		struct thread *owner = frame_table[frame_idx].owner;
		if (upage_to_evict == NULL) 
			return NULL;

		kpage = pagedir_get_page (owner->pagedir, upage_to_evict);
		if (kpage == NULL)
			return NULL;

		/* If necessary, write the page to the file system or to swap. */
		struct page *p = page_lookup (upage_to_evict, owner);
		swap_out (p);

		pagedir_clear_page (owner->pagedir, upage_to_evict);

		/* This should be done after swap out. */
		if (zero)
			memset (kpage, 0, sizeof (PGSIZE));
	}

	return kpage;
}

/* Returns a frame index corresponding to 
	 kernel virtual address KPAGE. */
size_t get_frame_index (void *kpage)
{
	extern uint8_t *user_pool_base; /* set in palloc.c */
	ASSERT (is_kernel_vaddr (kpage));
	
	return (kpage - (void *) user_pool_base) / PGSIZE;
}

/* Adds a mapping in page directory,
   and set frame table entry. */
bool frametable_set_frame (void *upage, void *kpage, bool writable)
{
	/* Lock should be acquired before calling this function. */
	if (!lock_held_by_current_thread (&frame_table_lock))
		return false;

	ASSERT (is_user_vaddr (upage));
	ASSERT (is_kernel_vaddr (kpage));

	size_t f_idx = get_frame_index (kpage);
	ASSERT (f_idx < frame_table_length);	
	
	/* Insert page information. */
	if (!page_insert (upage, kpage, writable))
		return false;

	/* Set corresponding frame table entry. */
	frame_table[f_idx].upage = upage;
	frame_table[f_idx].owner = thread_current ();

	lock_release (&frame_table_lock);

	return true;
}

/* Frees a frame. 
	 Not only frame table entry is cleared,
	 but also corresponding page is freed. */
void free_frame (void *kpage)
{
	/* Lock should be acquired before this function is called. */
	ASSERT (lock_held_by_current_thread (&frame_table_lock));

	size_t f_idx = get_frame_index (kpage); 
	ASSERT (f_idx < frame_table_length);

	palloc_free_page (kpage);

	frame_table[f_idx].upage = NULL;
	frame_table[f_idx].owner = NULL;

	lock_release (&frame_table_lock);
}

/* Clears all frame table entries 
	 which belongs to currently exiting thread.
	 Called in process_exit (). */
void clear_frame_table (void)
{
	struct thread *cur = thread_current ();

	//lock_acquire (&frame_table_lock);

	uint32_t i;
	for (i=0; i<frame_table_length; i++)
	{
		struct frame_table_entry *fte = frame_table + i;
		if (fte->upage != NULL && fte->owner == cur)
		{
			fte->upage = NULL;
			fte->owner = NULL;
		}
	}

	//lock_release (&frame_table_lock);
}

void frame_table_acquire (void)
{
	lock_acquire (&frame_table_lock);
}

void frame_table_release (void)
{
	lock_release (&frame_table_lock);
}

/* Chooses a frame to evict using clock algorithm, 
	 and returns its index. */
uint32_t get_frame_to_evict (void)
{	
	/* This function is called only in get_frame () 
		 in which frame table lock is acquired. */
	ASSERT (lock_held_by_current_thread (&frame_table_lock));
	ASSERT (is_frame_table_full ());

	struct thread *t = thread_current ();

	while (true)
	{
		void *upage = frame_table[next_frame_idx].upage;

		if (upage != NULL)
		{
			/* Find a frame whose access bit is set to zero. */
			if (!pagedir_is_accessed (t->pagedir, upage))
			{
				break;
			}
			else
			{
				pagedir_set_accessed (t->pagedir, upage, false);
			}
		}

		next_frame_idx = (next_frame_idx + 1) % frame_table_length;
	}

	uint32_t ret = next_frame_idx;

	/* Make frame pointer point to next frame. */
	next_frame_idx = (next_frame_idx + 1) % frame_table_length;

	return ret;
}

bool is_frame_table_full (void)
{
	bool full = true;
	uint32_t i;
	for (i=0; i<frame_table_length; i++)
	{
		if (frame_table[i].upage == NULL)
		{
			full = false;
			break;
		}
	}

	return full;
}
#ifdef _TEST_
void print_frame_usage_(void)
{
	uint32_t i;
	printf("Start frame index = %d\n", next_frame_idx);
	for(i = 0; i < frame_table_length; i++)
	{
		if(frame_table[i].upage)
		{
			struct page* p;
			p = page_lookup(frame_table[i].upage, frame_table[i].owner);
			printf("frame index : %d, user addr : %p, use bit : %d\n", 
					get_frame_index(get_kpage(p)),
					frame_table[i].upage, 
					pagedir_is_accessed (frame_table[i].owner->pagedir,
																frame_table[i].upage));
		}
	}
}
#endif
